计算机科学PSPACE 完全复杂度类本页总览PSPACE 完全复杂度类阐述 称一个问题 B 是 PSPACE 完全的，如果它 满足 它是一个 PSPACE 问题 所有 PSPACE 中的 A 都能多项式时间归约为 B。 证明 如果 BBB 是 PSPACE 完全的且 B≤PCB\le_P CB≤PC 对于某个 C∈NPC\in NPC∈NP，则 CCC 是 PSPACE 完全的。 与 NP 完全复杂度类类似，我们经常需要将 TQBF 问题归约为某个语言来证明它是 NP 完全的。 实例 TQBF 问题 公式游戏问题 广义地理问题 性质 相关内容 参考文献